/*
 * @lc app=leetcode.cn id=433 lang=cpp
 *
 * [433] 最小基因变化
 */

// @lc code=start
class Solution
{
public:
    typedef pair<string, int> PII;

    int minMutation(string start, string end, vector<string> &bank)
    {
        unordered_set<string> bank_set(bank.begin(), bank.end());

        if (start == end)
            return 0;
        if (!bank_set.count(end))
            return -1;

        char keys[] = {'A', 'C', 'G', 'T'};
        unordered_set<string> visited;
        queue<PII> que({PII(start, 0)});
        visited.insert(start);

        while (!que.empty())
        {
            PII curr = que.front();
            que.pop();
            if (curr.first == end)
                return curr.second;
            for (int i = 0; i < 8; i++)
            {
                for (int k = 0; k < 4; k++)
                {
                    if (curr.first[i] == keys[k])
                        continue;
                    string next = curr.first;
                    next[i] = keys[k];
                    if (bank_set.count(next) == 0)
                        continue;
                    if (visited.count(next))
                        continue;
                    que.push(PII(next, curr.second + 1));
                    visited.insert(next);
                }
            }
        }

        return -1;
    }
};
// @lc code=end
